/*
 * Copyright (C), 2015-2018
 * FileName: Solution067
 * Author:   zhao
 * Date:     2018/9/5 11:49
 * Description: 67. 二进制求和
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈67. 二进制求和〉
 *
 * @author zhao
 * @date 2018/9/5 11:49
 * @since 1.0.1
 */
public class Solution067 {
  /**************************************
   * 题目
   给定两个二进制字符串，返回他们的和（用二进制表示）。

   输入为非空字符串且只包含数字 1 和 0。

   示例 1:

   输入: a = "11", b = "1"
   输出: "100"
   示例 2:

   输入: a = "1010", b = "1011"
   输出: "10101"
   **************************************/

  /**************************************
   *
   * 想法：
   *      1. 像67题一样进行递归
   *      2. 直接使用for循环操作
   *
   *      判断加和，然后余数为数，商为进位数
   *
   * 我的做法：
   *      超过15.7%的测试案例
   *  总结：
   *      1. 判断是否越界，越界即为0，省掉了交换ab值的过程
   *      2. char可以直接相减
   *      3. StringBuilder的insert方法可以使用 append方法和reverse方法代替
   * ***********************************/
  public String addBinary(String a, String b) {
    // 这里运行完成之后b的长度肯定小于a的长度
    if (b.length() > a.length()) {
      String c = b;
      b = a;
      a = c;
    }
    int lengthA = a.length();
    int lengthB = b.length();
    int balanceAB = lengthA - lengthB;
    // 上一个是否进位
    boolean isCarry = false;

    StringBuilder stringBuilder = new StringBuilder();

    for (int j = lengthA - 1; j > -1; j--) {
      int temp = 0;

      char strA = a.charAt(j);
      int indexB = j - balanceAB;
      char strB = indexB < 0 ? '0' : b.charAt(indexB);

      // 判断进位
      if (strA == '1' && strB == '1') {
        temp = 2;
      } else if (strA == '0' && strB == '0') {
      } else {
        temp = 1;
      }
      // 如果之前有进位
      if (isCarry) {
        temp++;
      }

      int value = temp % 2;
      isCarry = temp / 2 > 0;

      stringBuilder.insert(0, value);
    }

    // 第一位还有进位
    if (isCarry) {
      stringBuilder.insert(0, 1);
    }

    return stringBuilder.toString();
  }

  /**************************************
   * 比我好的答案
   * ***********************************/
  public String better(String a, String b) {
    int len1 = a.length(), len2 = b.length();
    StringBuilder sb = new StringBuilder();
    int i = len1 - 1, j = len2 - 1, carry = 0;
    while (i >= 0 || j >= 0) {
      // 判断是否越界
      // char可以直接相减
      int x = (i >= 0) ? a.charAt(i) - '0' : 0;
      int y = (j >= 0) ? b.charAt(j) - '0' : 0;
      int sum = x + y + carry;
      carry = sum / 2;
      sb.append(sum % 2);
      i--;
      j--;
    }
    if (carry > 0) {
      sb.append(carry);
    }
    return sb.reverse().toString();
  }
}
